/*
day89
2019.11.25
*/
#include<queue>
#include<vector>
using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};


class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> que;
        que.push(root); 
        int res;
        TreeNode *cur;
        
        while(!que.empty())
        {
        	int num=que.size();
        	cur=que.front();
        	res=cur->val;
        	for(int i=0;i<num;i++)
        	{
        		cur=que.front();
        		que.pop();
        		if(cur->left) que.push(cur->left);
        		if(cur->right) que.push(cur->right);
			}
		}
		
		return res;
    }
    
    int findBottomLeftValue2(TreeNode* root)
    {
    	int res=0,max=0;
    	int &res_r=res,&max_r=max;
    	help(root,max_r,1,res_r);
    	return res;
	} 
	
	void help(TreeNode *root,int &max,int curDepth,int &res)
	{
//		if(!root) return ;
		
		if(root->left) help(root->left,max,curDepth+1,res);
		
		if(root->right) help(root->right,max,curDepth+1,res);
		
		if(curDepth>max)
		{
			res=root->val;
			max=curDepth;
		}
	}
};


int main()
{
	return 0;
}
